package _18_剑指OfferII;

public class _020_剑指OfferII回文子字符串的个数 {

    public static void main(String[] args) {

        _020_剑指OfferII回文子字符串的个数 v = new _020_剑指OfferII回文子字符串的个数();

        String str = "aaa";
        System.out.println(v.countSubstrings(str));

    }

    // 动态规划, 对于回文子串，可以看到也是存在动态规划特性的
    // 存在最优子结构性质
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2) {
                      count++;
                      dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        count++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return count;
    }

    // 中心扩展法则 O(n^2)
    public int countSubstrings2(String s) {
        int len = s.length();
        int end = (len << 1) - 1;
        int count = 0;
        for (int i = 0; i < end; i++) {
            int left = i >> 1;
            int right = (i + 1) >> 1;
            // 中心扩展
            while (left >= 0 && right < len && s.charAt(left--) == s.charAt(right++)) count++;
        }
        return count;
    }

    // 循环遍历, 时间复杂度O(n^3)
    public int countSubstrings1(String s) {
        int len = s.length();
        int count = 0;
        for (int start = 0; start < len; start++) {
            for (int end = start; end < len; end++) {
                if (isPalindromic(s, start, end)) count++;
            }
        }
        return count;
    }

    public boolean isPalindromic(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

}
